package leetcode_周赛._2023._09;

import java.util.ArrayList;
import java.util.List;

/**
 * 第 362 场周赛 <p>
 * AC_1
 *
 * @author yezh
 * @date 2023/9/11 15:18
 */
public class _10 {

    /**
     * 2428.与车相交的点 <p>
     * 算法：差分数组
     * <p>给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [starti, endi] ，其中
     * starti 是第 i 辆车的起点，endi 是第 i 辆车的终点。
     * 返回数轴上被车 任意部分 覆盖的整数点的数目。</p>
     */
    public int numberOfPoints(List<List<Integer>> nums) {
        int[] prefix = new int[105];
        for (List<Integer> num : nums) {
            prefix[num.get(0)]++;
            prefix[num.get(1) + 1]--;
        }
        int ans = 0, s = 0;
        for (int num : prefix) {
            s += num;
            if (s > 0) ++ans;
        }
        return ans;
    }

    /**
     * 2849.判断能否在给定时间内到达单元格 <p />
     * 算法：贪心 <p />
     * 斜着走一步 = 水平走一步 + 垂直走一步 <p />
     */
    public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        if (sx == fx && sy == fy) return t != 1;
        return t >= Math.max(Math.abs(sx - fx), Math.abs(sy - fy));
    }

    /**
     * 2850.将石头分散到网格图的最少移动次数
     * 算法：回溯
     * 类似全排列
     */
    public int minimumMoves(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        List<int[]> l1 = new ArrayList<>(), l2 = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] > 1) for (int k = 0; k < grid[i][j] - 1; k++) l1.add(new int[]{i, j});
                else if (grid[i][j] == 0) l2.add(new int[]{i, j});
        ans = Integer.MAX_VALUE;
        dfs(new ArrayList<>(), new boolean[l1.size()], l1, l2);
        return ans;
    }

    int ans;

    void dfs(List<int[]> cur, boolean[] visited, List<int[]> l1, List<int[]> l2) {
        int size = l1.size();
        if (cur.size() == size) {
            int len = 0;
            for (int i = 0; i < size; i++)
                len += Math.abs(cur.get(i)[0] - l2.get(i)[0]) + Math.abs(cur.get(i)[1] - l2.get(i)[1]);
            ans = Math.min(ans, len);
        }
        for (int i = 0; i < size; i++) {
            if (visited[i]) continue;
            cur.add(l1.get(i));
            visited[i] = true;
            dfs(cur, visited, l1, l2);
            visited[i] = false;
            cur.remove(cur.size() - 1);
        }
    }

}
